package leetcode.code0420;

import java.util.PriorityQueue;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int strongPasswordChecker(String password) {
		char[] cs = password.toCharArray();
		int len = cs.length;
		if (len == 0) {
			// 啥都没有你个老六
			return 6;
		}
		// 缺失种类
		int type = this.missType(cs, len);
		char cur = cs[0], last = cur;
		int cnt = 1;// 连续的字符数量，计数
		int update = 0;// 如果都用更新方式断开连续的字符，需要多少次操作
		// %3==0删1少1更新，%3==1删2少1更新，%3==2删3少1更新，所以需要删除的话，当然删除%3较小的连续相同字符串。
		PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> a % 3 - b % 3);
		for (int i = 1; i <= len; i++) {
			if (i < len && (cur = cs[i]) == last) {
				cnt++;
			} else {
				if (cnt >= 3) {
					pq.add(cnt);
					update += cnt / 3;
				}
				cnt = 1;
				last = cur;
			}
		}
		// 至多20个，剩下rest个
		int rest = len;
		// 删除操作是能减少更新操作的。
		// rest > 20 才删。删除操作只有在%3==0时，和更新一个收益，能不删，就不删，尽量更新。
		// rest > 20 有得删，还有能被省下的更新，还有能删除的连续字符串
		while (rest > 20 && update > 0 && !pq.isEmpty()) {
			int num = pq.poll();
			if (num % 3 == 0) {
				update--;
			}
			rest--;
			if (--num >= 3) {
				pq.add(num);
			}
		}
		return Math.max(update, Math.max(type, 6 - len)) + Math.max(0, len - 20);
	}

	private int missType(char[] cs, int len) {
		// 至少包含一个小写字母一个大写字母和一个数字 。
		int upper = 0, lower = 0, digit = 0;
		char cur = 1;
		for (int i = 0; i < len; i++) {
			if ((cur = cs[i]) >= '0' && cur <= '9') {
				digit = 1;
			} else if (cur >= 'a' && cur <= 'z') {
				lower = 1;
			} else {
				upper = 1;
			}
		}
		// 缺失种类
		return 3 - upper - lower - digit;
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

	@Override
	public void debug4() {
		HelpDebug.compare(23, this.strongPasswordChecker("FFFFFFFFFFFFFFF11111111111111111111AAA"));
		HelpDebug.compare(2, this.strongPasswordChecker("1234567890123456Baaaa"));
		HelpDebug.compare(13, this.strongPasswordChecker("aaaaaaaAAAAAA6666bbbbaaaaaaABBC"));
		HelpDebug.compare(3, this.strongPasswordChecker("aA345123451234512AAAAA"));
		HelpDebug.compare(5, this.strongPasswordChecker("1"));
		HelpDebug.compare(5, this.strongPasswordChecker("A"));
		HelpDebug.compare(5, this.strongPasswordChecker("a"));
		HelpDebug.compare(6, this.strongPasswordChecker(""));
		HelpDebug.compare(4, this.strongPasswordChecker("AAAAAABBBBBB123456789a"));
		HelpDebug.compare(10, this.strongPasswordChecker("hoAISJDBVWD09232UHJEPODKNLADU1"));
		HelpDebug.compare(3, this.strongPasswordChecker("..."));

		HelpDebug.compare(2, this.strongPasswordChecker("qqq123qqq"));
		HelpDebug.compare(2, this.strongPasswordChecker("QQQQQ"));
		HelpDebug.compare(2, this.strongPasswordChecker("aaaaaa"));
		HelpDebug.compare(2, this.strongPasswordChecker("1010101010aaaB10101010"));
		HelpDebug.compare(7, this.strongPasswordChecker("aaaaaaaaaaaaaaaaaaaaa"));
		HelpDebug.compare(3, this.strongPasswordChecker("abababababababababaaa"));
		HelpDebug.compare(0, this.strongPasswordChecker("1337C0d3"));
		HelpDebug.compare(6, this.strongPasswordChecker("ABABABABABABABABABABABAB"));
		HelpDebug.compare(5, this.strongPasswordChecker("a"));
		HelpDebug.compare(3, this.strongPasswordChecker("aA1"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

}
